package cn.liberg.fastalgorithm.bit;

/**
 * 异或运算工具类
 * 位运算进阶参考：https://blog.csdn.net/linysuccess/article/details/105811530
 *
 * @author Liberg
 */
public class Xor {

    /**
     * 位运算只需单独考虑对应的每一位即可，异或在一起，某一位出现了奇数个1，最终结果该位就是1，否则是0
     *
     * 所以，不难得出4k^(4k+1)^(4k+2)^(4k+3) = 0
     * 也就是说，从0开始，连续4个整数一组，每一组内部异或结果为0
     *
     *  若n=4k， xor[1..n]=4k，即n本身
     *  若n=4k+1，xor[1..n]=4k ^ 4k+1=1
     *  若n=4k+2, xor[1..n]=1 ^ 4k+2 = n+1 （n=4k+2为偶数）
     *  若n=4k+3, xor[1..n]=4k+3 ^ 4k+3 = 0
     *
     *  @return 返回[0..n]范围内所有整数相异或的结果
     */
    public static int ofRange(int n) {
        switch (n&3) {
            case 0:
                return n;
            case 1:
                return 1;
            case 2:
                return n+1;
            default:
                return 0;
        }
    }

    /**
     * 计算xor[start...end]
     * 即xor[0,1,..,start-1] ^ xor[0,1,..,start-1,start,..,end]
     */
    public static int ofRange(int start, int end) {
        return ofRange(start-1) ^ ofRange(end);
    }
}
